package solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-08-22 13:07
 */
public class Solution_8other {

    /*===========================================================================================================================
     * 215. 数组中的第K个最大元素
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * 1.二叉堆 (优先队列实现)
     * 2.快速选择算法
     * */
    public int findKthLargest1(int[] nums, int k) {
        // 小顶堆，堆顶是最小元素
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        for (int num:nums) {
            pq.offer(num);
            // 堆中元素多于 k 个时，删除堆顶元素
            if (pq.size()>k){
                pq.poll();
            }
        }
        // pq 中剩下的是 nums 中 k 个最大元素，
        // 堆顶是最小的那个，即第 k 个最大元素
        return pq.peek();
    }

    //快排的复用
    int partition(int[] nums, int lo, int hi) {
        if (lo==hi) return lo;
        // 将 nums[lo] 作为默认分界点 pivot
        int pivot=nums[lo];
        // j = hi + 1 因为 while 中会先执行 --
        int i=lo,j=hi+1;
        while (true){
            // 保证 nums[lo..i] 都小于 pivot
            while (nums[++i]<pivot){
                if (i==hi) break;}
            // 保证 nums[j..hi] 都大于 pivot
            while (nums[--j]>pivot){
                if (j==lo) break;
            }
            if (i>=j) break;
            // 如果走到这里，一定有：
            // nums[i] > pivot && nums[j] < pivot
            // 所以需要交换 nums[i] 和 nums[j]，
            // 保证 nums[lo..i] < pivot < nums[j..hi]
            swap(nums,i,j);
        }
        swap(nums,j,lo);
        return j;
    }
    // 交换数组中的两个元素
    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        //排序是从小到大：题目要求的是「第 k 个最大元素」，这个元素其实就是 nums 升序排序后「索引」为 len(nums) - k 的这个元素。
        k=nums.length-k;
        while (left<=right){
            int p=partition(nums,left,right);
            if (p<k){
                // 第 k 大的元素在 nums[p+1..hi] 中
                left=p+1;
            }else if (p>k){
                // 第 k 大的元素在 nums[lo..p-1] 中
                right=p-1;
            }else if (p==k){
                return nums[p];
            }
        }
        return -1;
    }

    /*===========================================================================================================================
     * 241. 为运算表达式设计优先级
     * 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
     * 按照每个运算符来分割表达式
     * */
    // 备忘录
    HashMap<String,List<Integer>> memo=new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        if (memo.containsKey(expression)) {
            return memo.get(expression);
        }
        List<Integer> res=new LinkedList<>();
        for (int i = 0; i < expression.length(); i++) {
            char cur=expression.charAt(i);
            if (cur=='-'||cur=='+'||cur=='*'){
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                for (int a:left){
                    for (int b:right) {
                        if (cur=='+'){  res.add(a+b);}
                        else if (cur=='-') {    res.add(a-b);}
                        else if (cur=='*'){     res.add(a*b);}
                    }
                }
            }
        }
        if (res.isEmpty()){
            // 如果 res 为空，说明算式是一个数字，没有运算符
            res.add(Integer.parseInt(expression));
        }
        memo.put(expression,res);
        return res;
    }




    /*===========================================================================================================================
     *颠倒二进制位
     * 双指针，前后交换
     * */
    public int reverseBits(int n) {
        int res=0;
        for (int i = 0; i < 32; i++) {
            res<<=1;
            res|=n&1;
            n>>=1;
        }
        return res;
    }

    /*===========================================================================================================================
     *杨辉三角
     * */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> row0=new ArrayList<>();
        row0.add(0,1);
        lists.add(row0);
        for (int i = 1; i < numRows; i++) {
            ArrayList<Integer> row=new ArrayList<>();
            row.add(0,1);
            for (int j = 1; j < i; j++) {
                row.add(j,lists.get(i-1).get(j)+lists.get(i-1).get(j-1));
            }
            row.add(i,1);
            lists.add(row);
        }
        return lists;
    }


    /*===========================================================================================================================
     *有效的括号
     * 使用堆栈
     * */
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char sc=s.charAt(i);
            if (sc=='(')
                stack.push(')');
            else if (sc=='{')
                stack.push('}');
            else if (sc=='[')
                stack.push(']');
            else if (stack.isEmpty()||stack.pop()!=sc){
                return false;
            }
        }
        return stack.isEmpty();
    }



    public static void main(String[] args) {
        int n=00000000000000000000000000001011;
        String s="()[]{}";
        int[] nums= new int[]{3,0,1};

        Solution_8other solution=new Solution_8other();
//        System.out.println(solution.hammingWeight(n));
//        System.out.println(solution.hammingDistance(1,4));
//        System.out.println(solution.reverseBits(n));
//        System.out.println(solution.generate(5).toString());
//        System.out.println(solution.isValid(s));

    }


}
